//
// Created by cheng on 2021/02/24.
// 二叉树的遍历
//

#include <iostream>
#include <unordered_map>
#include <queue>
#include <stack>
#define ElemType char
using namespace std;

/**
 * 二叉树
 */
typedef struct BiTNode{
    ElemType data;
    struct BiTNode* lChild, * rChild;
} BiTNode, *BiTree;

/**
 * 访问结点
 * @param node
 */
void visit(BiTNode* node);

/**
 * 线序遍历
 * 递归算法
 * @param t
 */
void PreOrder_Recursion(BiTree& tree);

/**
 * 线序遍历
 * 非递归算法
 * @param t
 */
void PreOrder(BiTree& tree);

/**
 * 中序遍历
 * @param t
 */
void InOrder_Recursion(BiTree& tree);

/**
 * 中序遍历
 * 非递归算法
 * @param t
 */
void InOrder(BiTree& tree);

/**
 * 后序遍历
 * @param t
 */
void PostOrder_Recursion(BiTree& tree);

/**
 * 后序遍历
 * 非递归算法
 * @param t
 */
void PostOrder(BiTree& tree);

/**
 * 层序遍历
 * @param t
 */
void LevelOrder(BiTree& tree);

/**
 * 初始化二叉树
 * @param t
 */
void InitBiTree(BiTree& tree);

/**
 * 先序遍历创建二叉树
 * @param t
 */
void PreBuildBiTree(BiTree& tree);

void visit(BiTNode* node) {
    std::cout << node->data << " ";
}

void PreOrder_Recursion(BiTree& t) {
    if (t != nullptr) {
        visit(t);
        PreOrder_Recursion(t->lChild);
        PreOrder_Recursion(t->rChild);
    }
}

void InOrder_Recursion(BiTree& t) {
    if (t != nullptr) {
        InOrder_Recursion(t->lChild);
        visit(t);
        InOrder_Recursion(t->rChild);
    }
}

void PostOrder_Recursion(BiTree& t) {
    if (t != nullptr) {
        PostOrder_Recursion(t->lChild);
        PostOrder_Recursion(t->rChild);
        visit(t);
    }
}

void LevelOrder(BiTree& t) {
    std::queue<BiTNode*> queue; // 初始化队列
    queue.push(t); // 将根结点放入队列

    while (!queue.empty()) {
        auto p = queue.front();
        visit(p);
        queue.pop();
        if (p->lChild != nullptr) {
            queue.push(p->lChild);
        }
        if (p->rChild != nullptr) {
            queue.push(p->rChild);
        }
    }
}

void PreBuildBiTree(BiTree &t) {
    ElemType c = std::cin.get();
    if (c == '#') {
        delete t;
        t = nullptr;
    } else {
        t->lChild = new BiTNode{'\0', nullptr, nullptr};
        t->rChild = new BiTNode{'\0', nullptr, nullptr};
        t->data = c;
        PreBuildBiTree(t->lChild);
        PreBuildBiTree(t->rChild);
    }
}

void InitBiTree(BiTree &t) {
    t = new BiTNode{'\0', nullptr, nullptr};
}

void PreOrder(BiTree &tree) {
    std::stack<BiTNode*> stack;
    auto p = tree;
    while (p != nullptr || !stack.empty()) {
        if (p != nullptr) { // 一路向左
            stack.push(p);
            visit(p); // 访问当前结点
            p = p->lChild;
        } else { // 左结点为空
            p = stack.top();
            stack.pop();
            p = p->rChild; // 往右结点移动一位
        }
    }
}

void InOrder(BiTree &tree) {
    std::stack<BiTNode*> stack;
    auto p = tree;
    while (p != nullptr || !stack.empty()) {
        if (p != nullptr) { // 一路向左，结点入栈
            stack.push(p);
            p = p->lChild;
        } else { // 左结点为空，访问栈顶结点
            p = stack.top();
            visit(p);
            stack.pop();
            p = p->rChild; // 向右子树走一个结点
        }
    }
}

void PostOrder(BiTree &tree) {
    BiTNode* lastNode = nullptr; // 记录上一个被访问的结点
    auto p = tree;
    std::stack<BiTNode*> stack;
    while (!stack.empty() || p != nullptr) {
        if (p != nullptr) { // 把所有的左结点加入栈
            stack.push(p);
            p = p->lChild;
        } else {
            p = stack.top();
            // 如果右结点存在且没有被访问过，入栈
            if (p->rChild != nullptr && p->rChild != lastNode) {
                p = p->rChild;
                stack.push(p);
                p = p->lChild;
            } else { // 如果左右结点不存在，访问该结点，并出栈
                visit(p);
                lastNode = p; // 标记该节点为被访问状态
                p = nullptr;
                stack.pop();
            }
        }
    }
    std::cout << std::endl;
}